package day_2023_7_to_10;

/**
 * @author haomin
 * @date 2023/08/11 23:46
 **/
public class Day_8_11 {
    class Solution {
        int mod = (int)1e9 + 7;
        public int fib(int n) {
            if(n <= 1) return n == 1 ? 1 : 0;
            int[] dp = new int[n + 1];
            dp[0] = 0;
            dp[1] = 1;
            for(int i = 2; i <= n; ++i) {
                dp[i] = (dp[i-2] + dp[i-1]) % mod;
            }
            return dp[n];
        }
    }
    class Solution2 {
        int mod = (int)1e9 + 7;
        public int numWays(int n) {
            if(n <= 2) return n == 2 ? 2 : 1;
            int[] dp = new int[n+1];
            dp[0] = dp[1] = 1;
            for(int i = 2; i <= n; ++i) {
                dp[i] = (dp[i-2] + dp[i-1]) % mod;
            }
            return dp[n];
        }
    }
}